package code1.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class P130 {

    //关键：如何判断一块区域是否被X包围
    //如果有边界上的点，那么就没有被包围；如果没有边界上的点，那么就一定是被X包围了

    int n,m;
    boolean[][] visited;
    boolean flag = false;        //flag表示当前'O'区域是否有边界上的O
    int[][] go={{1,0},{-1,0},{0,-1},{0,1}};

    void bfs(int x,int y,List<int[]> list,char[][] board){
        Queue<int[]> queue=new LinkedList<>();
        visited[x][y]=true;
        list.add(new int[]{x,y});
        queue.offer(new int[]{x,y});
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            if(point[0]==0 || point[0]==n-1 || point[1]==0 || point[1]==m-1){
                flag=true;          //说明当前区域存在边界上的O
            }
            for(int i=0;i<4;i++){
                int nextx=point[0]+go[i][0];
                int nexty=point[1]+go[i][1];
                if(nextx>=0 && nextx<n && nexty>=0 && nexty<m && board[nextx][nexty]=='O' && !visited[nextx][nexty]){
                    visited[nextx][nexty]=true;
                    list.add(new int[]{nextx,nexty});
                    queue.offer(new int[]{nextx,nexty});
                }
            }
        }
    }

    public void solve(char[][] board) {
        n=board.length;
        m=board[0].length;
        visited=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!visited[i][j] && board[i][j]=='O'){
                    flag=false;
                    List<int[]> list=new ArrayList<>();
                    bfs(i,j,list,board);
                    if(!flag){
                        //如果当前区域不存在边界上的O,就将当前区域的O填为X
                        for(int k=0;k<list.size();k++){
                            int[] point = list.get(k);
                            board[point[0]][point[1]]='X';
                        }
                    }
                }
            }
        }
    }
}
